package leetcode.D100.T94;

import util.TreeNode;

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

/**
 * @File Info: leetcode -- <Solution>
 * @Author: DYZ
 * @Create: 2021-08-18 9:57:44 星期三
 */

public class Solution {
    /**
     * 解法1：递归
     */
    /*public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> results = new ArrayList<>();
        inorder(root, results);
        return results;
    }

    private void inorder(TreeNode root, List<Integer> results) {
        if(root == null) {
            return;
        }
        inorder(root.left, results);
        results.add(root.val);
        inorder(root.right, results);
    }*/

    /**
     * 解法2：迭代
     * @param root
     * @return
     */
    /*public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> results = new ArrayList<>();
        if(root == null) {
            return results;
        }
        Deque<TreeNode> dq = new LinkedList<>();
        dq.addFirst(root);
        while (!dq.isEmpty()) {
            TreeNode top = dq.getFirst();
            if(top.left != null) {
                dq.addFirst(top.left);
                top.left = null;
                continue;
            }
            results.add(top.val);
            dq.removeFirst();
            if(top.right != null) {
                dq.addFirst(top.right);
                top.right = null;
                continue;
            }
        }
        return results;
    }*/

    // 二刷 迭代解法
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        Deque<TreeNode> stack = new LinkedList<>();
        TreeNode cur = root;
        while (cur != null || !stack.isEmpty()) {
            while (cur != null) {
                stack.push(cur);
                cur = cur.left;
            }
            cur = stack.pop();
            result.add(cur.val);
            cur = cur.right;
        }
        return result;
    }
}
